﻿using System;

namespace _20234_14快排递归
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            int[] arr = { 1,1,6,6,2,2,3,3 };
            QuicSort(ref arr, 0, arr.Length - 1);
        }





        static void Swap(ref int[]arr,int a,int b)
        {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

        static int GetMiddle(int left,int right)
        {
            return (left + right) / 2;
        }

        static void QuicSort(ref int[] arr,int left,int right)
        {
            if(left>=right)
            {
                return;
            }
            int nextLeft = left;
            int nextRight = right;
            int key = GetMiddle(left, right);
            Swap(ref arr, left, key);
            key = left;
            while (left < right)
            {
                while (arr[right] > arr[key] && left < right)
                    right--;
                while (arr[left] <= arr[key] && left < right)
                    left++;
                Swap(ref arr, left, right);
            }
            Swap(ref arr, key, left);
            QuicSort(ref arr, nextLeft, left - 1);
            QuicSort(ref arr, left + 1, nextRight);

        }

    }
}
